|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ グラフ理論 ： [ぐらふりろん] (n) graph theory ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough ・ 理 ： [り] 【名詞】 1. reason ・ 理論 ： [りろん] 【名詞】 1. theory ・ 論 ： [ろん] 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment
グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。 厳密に述べると次のようになる。(''r'',''g'')-グラフとは任意の頂点が相異なる''r''個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さが''g''に一致するものを指す。任意の''r'' ≥ 2、''g'' ≥ 3に対して(r,g)-グラフは存在することが知られている。(''r'',''g'')-ケージとは(''r'',''g'')-グラフのうちもっとも頂点数が少ないグラフのことである。 次数''r''、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は : 以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は : 以上となる。また''r''と''g''の組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージはバラバン10-ケージ、Harries graphとHarries-Wong graphの同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となるバラバン11-ケージのみである。 == 具体例 == 次数1のグラフはサイクルを持たない。次数2のグラフはサイクルそのもので内周は頂点数に一致する。そのため''r'' ≥ 3の場合についてケージを考える。(''r'',3)-ケージは頂点数r+1の完全グラフ''K''''r''+1となる。また(''r'',4)-ケージは頂点数2''r''の完全二部グラフ''K''''r'',''r''となる。 他の特筆すべきケージ（ムーアグラフを含む。）: * (3,5)-ケージ: ピーターセングラフ、頂点数10 * (3,6)-ケージ: ヒーウッドグラフ、頂点数14 * (3,8)-ケージ: Tutte–Coxeter graph、頂点数30 * (3,10)-ケージ: バラバン10-ケージ、頂点数70 * (4,5)-ケージ: ロバートソングラフ、頂点数19 * (7,5)-ケージ: ホフマン-シングルトングラフ、頂点数50 * ''r''-1が素数のべき乗のとき、(''r'',6)-ケージは射影平面のインシデント・グラフとなる。 * ''r''-1が素数のべき乗のとき、(''r'',8)-ケージと(''r'',12)-ケージは一般化多角形となる。 ''r'' > 2かつ''g'' > 2の場合に知られている(''r'',''g'')-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ケージ (グラフ理論)」の詳細全文を読む スポンサード リンク
|